COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0BDR25\M1BDJ25\M2BDR25X\M3SUB\M4NGR30\M5NGR40\F0
C00031 ENDMK
C⊗;
\\M0BDR25;\M1BDJ25;\M2BDR25X;\M3SUB;\M4NGR30;\M5NGR40;\F0
(This version of this chapter is very incomplete and preliminary.)

\F5\CCHAPTER IV

\CLISP SELF-APPLIED


\F41. The list representation of LISP functions.\F0

\J	When one computes with symbolic expressions, it is necessary to face
the fact that the most convenient notation for reading and writing is not
the most convenient notation for symbolic data from the point of view of the
programmer who must write programs for manipulating the data.  So far, we have
resolved this dilemma by using S-expressions for data and writing LISP functions
and programs in a language that is hopefully convenient for reading and writing.
Now LISP programs are also symbolic information, and we want to be able to
manipulate LISP programs with LISP functions and programs.  In order to do this
we use a representation of LISP functions by LISP lists.  In Chapter 6, we shall
discuss procedures for translating between S-expression notation and other
notations for symbolic information.

	We use the following conventions:

	1. Variables are represented by atomic symbols composed of upper case
letters.  Thus the variable \F1x\F0 will normally be represented by the
corresponding upper case letter X.

	2. An S-expression \F1e\F0 will be represented as (QUOTE \F1e\F0).  Thus
the atom X is represented by (QUOTE X).

	3. The basic LISP functions \F1car, cdr, cons, atom\F0 and \F1eq\F0, 
the functions \F1list\F0 and \F1null\F0 derived from them are represented by
writing the words in upper case.  Thus we have CAR, CDR, CONS, ATOM, EQ, LIST, 
and NULL.  Defined functions are also represented by atoms, e.g. ALT, DIFF, etc.

	4. Numbers are represented by the S-expression notation for numbers
without QUOTE, and the special atoms T and NIL are represented by themselves
without QUOTE. Avoiding QUOTE here is for convenience and can be regarded as
using variables T and NIL whose permanent values are the S-expressions T and
NIL.

	5. The application of a function to arguments is represented by a list
the first element of which is the function name and the remaining elements are
the arguments in the same order.  Thus \F1f[x, y]\F0 is represented by
(F X Y).\.

	6. The conditional expression

	\F2if\F1 p\F31\F2 then \F1e\F31\F1 ... \F2\;
else if \F1p\F3n\F2 then \F1e\F3n\F0

is represented by

	(COND (\F1p\F31\F1 e\F31\F1) ... (\F1p\F3n\F1 e\F3n\F0)).

There is no way of representing a final \F2else\F0, so

	\F2if\F1 p \F2then\F1 a \F2else \F1b\F0

is represented by

	(COND (\F1p a)(\F0T \F1b\F0)).

Thus

	\F2if n \F1u ∨ \F2n d \F1u \F2then\F1 u \F2else a\;
 \F1u . \F1alt \F2dd \F1u\F0

is represented by

	(COND ((OR (NULL U) (NULL (CDR U))) U) (T (CONS (CAR U) (ALT (CDDR U))))).

\J	7. The λ-expression λ\F1x...z: \F0 is represented by
(LAMBDA (X ... Z) \F1e\F0).  Thus\.

	λ\F1x y: \F2if n \F1x \F2 then \F1y \;
\F2else a \F1x . append[\F2d \F1x, y]\F0

is represented by

	(LAMBDA (X Y) (COND ((NULL X) Y) (T (CONS (CAR X) (APPEND (CDR X) Y)))))).

\J	8. Finally, \F2label\F1[fname, e]\F0 is represented by (LABEL \F1fname e), 
so that\.

	\F2label\F1[alt, \F0λ\F1x: \F2if n \F1x ∨ \F2n d \F1x \F2then \F1x\;
 \F2else a \F1x . alt[\F2dd\F1 x]]\F0

is represented by

	(LABEL ALT (LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X)
		(T (CONS (CAR X) (ALT (CDDR X))))))).

\J	Actually, \F2label\F0 is rarely used in LISP programming, 
because it names a function for immediate use only, and usually one
wants to attach a function definition to its name for later use in
several places in the program.  The notation for making definitions varies
with the implementation of LISP.


\F42. The function \F1eval\F0.

	Except for speed and memory size all present day stored program
computers are equivalent in what computations they can do.  A program
written for one computer can be translated to run on another.  Indeed, 
one can write a simulator for one computer to run on another.  To put it
in commercial terms, no computer manufacturer can advertise that his machine
can do calculations impossible on the machine made by his competitors.

	This is well known intuitively, and the first mathematical theorem
of this kind was proved by A.M. Turing (1936), who defined a primitive kind
of computer now called a Turing machine, and showed how to make a universal
machine that could do any computation done by any Turing machine when given
a description of the machine to be simulated and the initial tape of the
computation to be imitated.

	In LISP the function \F1eval\F0 is a universal LISP function in the
sense that any computation done by any LISP function can be done by
\F1eval\F0 when \F1eval\F0 is given suitable arguments.

	\F1eval\F0 has two arguments the first of which is a LISP expression
in the notation given in the previous section, while the second is a list of
pairs that give the values of any free variables that may occur in the
expression.  Since any computation can be described as evaluating an expression
without free variables, the second argument plays a role mainly in the
recursive definition of \F1eval\F0, and we can start our computations with
the second argument NIL.

	To illustrate this, suppose we want to apply the function \F1alt\F0
to the list (A B C D E), i.e. we wish to evaluate \F1alt\F0[(A B C D E)].
This can be obtained by computing

	\F1eval\F0[((LABEL ALT (LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X)
(T (CONS (CAR X) (ALT (CDDR X))))))) (QUOTE (A B C D E)), NIL], 

and gives the expected result (A C E).
The second argument of \F1eval\F0, taken as NIL in the above example is a list
of dotted pairs where the first element of each pair is an atom representing
a variable and the second element is the value assigned to that variable.
A variable may occur more than once in the list and the value chosen is that
paired with the first occurrence of the variable.  We illustrate this by
the equation

	\F1eval\F0[(CAR X), ((X.(B.C)) (Y.A) (X.B))] = B, 

i.e. we have evaluated \F2a \F1x\F0 with \F1 x\F0 = (B.C).  The value associated
with a variable in such a list of pairs is computed by the auxiliary function
\F1assoc\F0 which has the recursive definition\.

	\F1assoc[v, a] ← \F2if n \F1a \F2then \F0NIL \F2else if aa \F1a\;
\F2 eq \F1v \F2then a \F1a \F2else \F1alt[v, \F2d \F1a]\F0.

Thus we have \F1assoc\F0[X, ((X.(B.C)) (Y.A) (X.B))] = (X.(B.C)).

	A simplified version of the usual LISP \F1eval\F0 is the following:

\F1eval[e, a] ←
	\F2if at \F1e \F2then \F0[\F2if numberp \F1e ∨ e\;
 \F2eq \F0NIL ∨ \F1e \F2eq \F0T \F2then \F1e \F2else\F1 assoc[e, a]]
	\F2else if at a\F1 e \F2then
		\F1[\F2if a \F1e\F2 eq \F0CAR \F2then a \F1eval[\F2ad \F1e, a]
		\F2else if a \F1e\F2 eq \F0CDR \F2then d \F1eval[\F2ad \F1e, a]
		\F2else if a \F1e\F2 eq \F0CONS \F2then \F1eval[\F2ad \F1e, a]\;
 . eval[\F2add \F1e, a]
		\F2else if a \F1e\F2 eq \F0ATOM \F2then at \F1eval[\F2ad \F1e, a]
		\F2else if a \F1e\F2 eq \F0EQ \F2then at \F1eval[\F2ad \F1e, a]\;
 \F2eq \F1eval[\F2add \F1e, a]
		\F2else if a \F1e\F2 eq \F0QUOTE \F2then ad \F1e
		\F2else if a \F1e\F2 eq \F0COND \F2then \F1evcon[\F2d \F1e, a]
		\F2else if a \F1e\F2 eq \F0LIST \F2then \F1mapcar[\F2d \F1e, \;
λx: eval[x, a]]
		\F2else \F1eval[\F2d \F1assoc[\F2a \F1e, a] . \F2d \F1e, a]]
	\F2else if aa \F1e \F2eq \F0LAMBDA \F2then\;
 \F1eval[\F2adda \F1e, prup[\F2ada \F1e, mapcar[\F2d \F1e, λx: eval[x, a]]] . a]
	\F2else if aa \F1e \F2eq \F0LABEL \F2then\;
\F1eval[\F2adda \F1e . \F2d \F1e, [\F2ada \F1e . \F2a \F1e] . a]\F0, 

where the auxiliary function \F1evcon\F0 is defined by

	\F1evcon[u, a] ← \F2if \F1eval[\F2aa \F1u, a] \F2then \F1eval[\F2ada \F1u, a]\;
 \F2else \F1evcon[\F2d \F1u, a]\F0, 

\Jand the auxiliary function \F1prup\F0 used for pairing up the elements of two
lists of equal length is defined by\.

	\F1prup[u, v] ← \F2if n \F1u \F2then \F0NIL \F2else \F1[\F2a \F1u\;
 . \F2a \F1v] . prup[\F2d \F1u, \F2d \F1u].\F0

\J	The way \F1eval\F0 works should be clear; atoms are either immediately
evaluable or have to be looked up on the list \F1a\F0; expressions whose first
term is one of the elementary functions are evaluated by performing the indicated
operation on the result of evaluating the arguments; \F1list\F0 has to be
handled specially, because it has an indefinite number of arguments; conditionals
are handled by an auxiliary function that evaluates the terms in the right order;
quoted S-expressions are trivial; non-elementary functions have their definitions
looked up on \F1a\F0 and substituted for their names; when a function is specified
by a λ, the inner expression is evaluated with a new \F1a\F0 which is obtained
by evaluating the arguments and pairing them up with the variables and putting
them on the front of the old \F1a\F0; and finally, \F2label\F0 is handled by
pairing the name of the function with the expression on \F1a\F0 and replacing
the whole function by the λ-part.

	\F1eval\F0 plays both a theoretical and a practical role in LISP.
Historically, the list notation for LISP functions and \F1eval\F0 were first
devised in order to show how easy it is to define a universal function in LISP -
the idea was to advocate LISP as an alternative to Turing machines for doing
the elementary theory of computability.  The notation used was chosen without
much regard for human convenience, because the original idea was purely
theoretical; the notation for conditional expressions, for example, has
an unnecessary extra level of parentheses.  However, S. R. Russell noted that
\F1eval\F0 could serve as an interpreter for LISP and promptly programmed it
in machine language with minor modifications for practical purposes.  Since
a compiler was long delayed, the interpreter was more easily modified and
handled some difficult cases with functional arguments better, an interpreter
based on \F1eval\F0 has remained a feature of most LISP systems.

	The way \F1eval\F0 handles arguments corresponds to the call-by-value
method of parameter passing in ALGOL and similar languages.  There is also
a form of \F1eval\F0 that corresponds to call-by-name.  Here it is:\.

	\F1neval[e, a] ← \F2if at \F1e\F2 then
		\F1[\F2if \F1e \F2eq \F0T \F2 then \F0T
		\F2else if \F1e \F2eq \F0NIL \F2then \F0NIL
		\F2else if \F1numberp e \F2then \F1e
		\F2else \F1neval[\F2d \F1assoc[e, a], a]]

	\F2else if at a \F1e \F2 then
		\F1[\F2if a \F1e \F2eq \F0CAR \F2then a \F1neval[\F2ad \F1e, a]
		\F2else if a \F1e \F2eq \F0CDR \F2then d \F1neval[\F2ad \F1e, a]
		\F2else if a \F1e \F2eq \F0CONS \F2then \F1neval[\F2ad \F1e, a]\;
 . neval[\F2add \F1e, a]
		\F2else if a \F1e \F2eq \F0ATOM \F2then at \F1neval[\F2ad \F1e, a]
		\F2else if a \F1e \F2eq \F0EQ \F2then \F1neval[\F2ad \F1e, a]\;
 \F2eq \F1neval[\F2add \F1e, a]
		\F2else if a \F1e \F2eq \F0QUOTE \F2then ad \F1e
		\F2else if a \F1e \F2eq \F0COND \F2then \F1nevcon[\F2d \F1e, a]
		\F2else if a \F1e \F2eq \F0LIST \F2then \F1mapcar[\F2d \F1e\;
, λx: neval[x, a]]
		\F2else \F1neval[\F2d \F1assoc[\F2a \F1e, a] . \F2d \F1e, a]]

	\F2else if aa \F1e \F2eq \F0LAMBDA \F2then \F1neval[\F2adda \F1e, \;
prup[\F2ada \F1e, \F2d \F1e] . a]

	\F2else if aa \F1e \F2eq \F0LABEL \F2then \F1neval[\F2adda \F1e\;
 . \F2d \F1e, [\F2ada \F1e . \F2a \F1e] . a], \F0

where the auxiliary function \F1nevcon\F0 is given by

	\F1nevcon[u, a] ← \F2if \F1neval[\F2aa \F1u, a] \F2then\;
 \F1neval[\F2ada \F1u, a] \F2else \F1nevcon[\F2d \F1u, a].\F0

\J	The difference between \F1eval\F0 and \F1neval\F0 is only in two terms.
\F1eval\F0 evaluates a variable by looking it up on the association list whereas
\F1neval\F0 looks it up on the association list and evaluates the result.
Correspondingly, when a λ-expression is encountered, \F1eval\F0 forms a new
association list by pairing the values of the arguments with the variables
bound by the λ and putting the new pairs in front of the old association list, 
whereas \F1neval\F0 pairs the arguments themselves with the
variables and puts them on the front of the association list.
In most cases both give the same result with the same work, but \F1neval\F0
gives a result in some cases in which \F1eval\F0 loops.  An example is
obtained by evaluating \F1F[2, 1]\F0 where \F1F\F0 is defined by\.

	\F1F[x, y] ← \F2if\F1 x=0 \F2then \F10 \F2else \F1F[x-1, F[y-2, x]].\F0

Exercises

\J	1. Write \F1neval\F0 and the necessary auxiliary functions in list
form, and try them out on some examples.



\F43. Computability.\F0

	Some LISP calculations run on indefinitely.  The most trivial
case occurs if we make the recursive definition\.

	\F1loop x ← loop x\F0

\Jand attempt to compute \F1loop[x]\F0 for any \F1x\F0 whatsoever.  Don't
dismiss this example just because no-one would
write such an obviously useless
function definition.  There is a sense in which it is the
"zero" of a large class of non¬terminating function definitions, and, 
as the Romans experienced but never learned, leaving zero out of the number
system is a mistake.

	Nevertheless, in most programming, non-terminating calculations are
the results of errors in defining functions.  Therefore, it would be
useful to be able to tell whether a function definition gives a
result for all arguments.  In fact, it would be useful to be able to tell
whether a function will terminate for a single argument.  Let us make
this goal more precise.

	Suppose that \F1f\F0 is a LISP function and \F1a\F0 is an S-expression, 
and we would like to know whether the computation of \F1f[a]\F0 terminates.
Suppose \F1f\F0 is represented by the S-expression \F1f*\F0 in the usual
S-expression notation for LISP functions.  Then the S-expression \F1(f* (QUOTE a))\F0
represents \F1f[a]\F0.  Define the function \F1term\F0 by giving
\F1term[e]\F0 the value \F2true\F1 if \F1e\F0 is an S-expression of the
form \F1(f* (QUOTE a))\F0 for which \F1f[a]\F0 terminates and \F2false\F0 otherwise.
We now ask whether \F1term\F0 is a LISP function, i.e. can it be constructed
from \F1car, cdr, cons, atom, \F0 and \F1eq\F0 using λ, \F2label\F0, and
conditional expressions?  Well, it can't, as we shall shortly prove, 
and this means that it is not \F1computable\F0 whether a LISP calculation
terminates, since if \F1term\F0 were computable by any computer or in any
recognized sense, it could be represented as a LISP function.  Here is the
proof:\.

	Consider the function \F1terma\F0 defined from \F1term\F0 by

	\F1terma u ← \F2if\F1 term list[u, list[\F0QUOTE\F1, u]] \F2then\F1 loop u\;
 \F2else true\F0, 

\Jand suppose that \F1f\F0 is a LISP function and that \F1f*\F0 is its
S-expression representation.  What is \F1terma f*\F0?
Well \F1terma f*\F0 tells us whether the computation of \F1f[f*]\F0
terminates, and it tells us this by going into a loop if \F1f[f*]\F0
terminates and giving \F2true\F0 otherwise.  Now if \F1term\F0 were
a LISP function, then \F1terma\F0 would also be a LISP function.  Indeed if
\F1term\F0 were represented by the S-expression \F1term*\F0, then
\F1terma\F0 would be represented by the S-expression\.

	\F1terma\F0* = (LAMBDA (U) (COND ((\F1term*\F0 (LIST U \;
(LIST (QUOTE QUOTE) U))) (LOOP U)) (T T))).

\JNow consider \F1terma[terma*]\F0.  According to the definition of \F1terma\F0, 
this will tell us whether \F1terma[terma*]\F0 is defined, i.e. it tells
about itself.  However, it gives this answer in a contradictory way; namely
\F1terma[terma*]\F0 looping tells us that \F1terma[terma*]\F0 terminates, 
and \F1terma[terma*]\F0 being \F2true\F1 tells us that \F1terma[terma*]\F0
doesn't terminate.  This contradiction tells us that \F1term\F0 is not a
LISP function, and there is no general procedure for telling whether
a LISP calculation terminates.

	The above result does not exclude LISP functions that tell whether
LISP calculations terminate.  It just excludes perfect ones.  Suppose
we have a function \F1t\F0 that sometimes says calculations terminate, 
sometimes says they don't terminate, and sometimes runs on indefinitely.
We shall further assume that when \F1t\F0 gives an
answer it is always right.  Given such a function we can improve it a bit
so that it will always give the right answer when the calculation it is
asked about terminates.  This is done by mixing the computation of \F1t[e]\F0
with a computation of \F1eval[e, \F0NIL] doing the computations
alternately.  If the \F1eval[e, \F0NIL] computation ever terminates, 
then the new function asserts termination.

	Given such a \F1t\F0, we can always find a calculation that
does not terminate but \F1t\F0 doesn't say so.  The construction is just like that
used in the previous proof.  Given \F1t\F0, we construct\.

	\F1ta u ← \F2if\F1 t list[u, list[\F0QUOTE\F1, u]] \F2then\F1 loop u\;
 \F2else true\F0, 

\Jand then we consider \F1ta[ta*]\F0.  If this had the value \F2true\F0, 
then it wouldn't terminate so therefore it doesn't terminate but is
not one of those expressions which \F1t\F0 decides.  Thus for any
partial decider we can find a LISP calculation which doesn't terminate
but which the decider doesn't decide.

	This can in turn be used to get a slightly better decider, namely\.

	\F1t\F31\F1[e] ← \F2if\F1 e = ta* \F2then \F0DOESN'T-TERMINATE\;
 \F2else\F1 t[e]\F0.

\JOf course, \F1t\F31\F0 isn't much better than \F1t\F0, since it can decide
only one more computation, but we can form \F1t\F32\F0 by applying the same
process, and so forth.  In fact, we can even form \F1t\F3∞\F0 which
decides all the cases decided by any \F1t\F3n\F0.  This can be further
improved by the same process, etc.  How far can we go?  The answer is
technical; namely, the improvement process can be carried out any
recursive ordinal number of times.

	Unfortunately, this kind of improvement seems to be superficial, 
since none of the new computations proved not to terminate are likely
to be of practical interest.
\.

Exercises.

1. Write a function that gives \F1t\F3n+1\F0 in terms of \F1t\F3n\F0.

2. Write a function that gives \F1t\F3∞\F0 in terms of \F1t\F0.